package leecode.array.二分查找问题;

/**
 * description:
 * author: wangxi
 * date:  2022/5/8 3:04 下午
 *
 * https://leetcode-cn.com/problems/sqrtx/
 **/
public class MySqrt {
    public int mySqrt(int x) {
        if (x < 0) {
            return -1;
        }
        // 平方根下 x需要满足 <= 0
        if (x == 0) {
            return 0;
        }
        // 下标从1开始
        int left = 1;
        int right = x;
        while (left <= right) {
            // 得用除法，乘法会超出时间限制，还会溢出
            int mid = (left + right) / 2;
            int temp = x/mid;
            if (temp == mid || ((x/(mid + 1) < (mid + 1)) && x/mid > mid) ) {
                return mid;
            } else if (temp > mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }

        }
        return -1;
    }
}
